Finite Automata
Q1.
Consider the following language: L= \{ w \in \{0,1\}^* \mid w \text{ ends with the substring } 011 \} Which one of the following deterministic finite automata accepts L?Q2.
Consider the following deterministic finite automaton (DFA)The number of strings of length 8 accepted by the above automaton is _________Q3.
Consider the language L over the alphabet {0, 1}, given below:L = \{w \in \{0, 1\}^* | w \text{ does not contain three or more consecutive 1's} \}. The minimum number of states in a Deterministic Finite-State Automaton (DFA) for L is _____.Q4.
Minimum number of states required in DFA accepting binary strings not ending in "101" isQ5.
Given a language L, define L^{i} as follows: L^{0}=\{\varepsilon \} L^{i}=L^{i-1} \cdot L for all i \gt 0 The order of a language L is defined as the smallest k such that L^{k}=L^{k+1}. Consider the language L1 (over alphabet 0) accepted by the following automaton. The order of L1 is ______Q6.
Suppose we want to design a synchronous circuit that processes a string of 0's and 1's. Given a string, it produces another string by replacing the first 1 in any subsequence of consecutive 1's by a 0. Consider the following example. \begin{array}{ll} \text{Input sequence:} & 00100011000011100 \\ \text{Output sequence:} & 00000001000001100 \end{array} A Mealy Machine is a state machine where both the next state and the output are functions of the present state and the current input. The above mentioned circuit can be designed as a two-state Mealy machine. The states in the Mealy machine can be represented using Boolean values 0 and 1. We denote the current state, the next state, the next incoming bit, and the output bit of the Mealy machine by the variables s, t, b and y respectively. Assume the initial state of the Mealy machine is 0. What are the Boolean expressions corresponding to t and y in terms of s and b?Q7.
The minimum possible number of states of a deterministic automaton that accepts the regular language L=\{w_{1}aw_{2}|w_{1},w_{2}\in \{a,b\}^{*},|w_{1}|=2,|w_{2}|\geq 3\} is ____Q8.
Let \delta denote that transition function and \hat{\delta} denote the extended transition function of the \epsilon- NFA whose transition table is given below: Then \hat{\delta}(q_{2},aba) is ____Q9.
Let \Sigma be the set of all bijections from {1,...,5} to {1,...,5}, where id denotes the identity function, i.e. id(j)=j,\forall j. Let \circ denote composition on functions. For a string x = x_1x_2 ... x_n \in \Sigma ^n, n \geq 0, let \pi(x) = x_1\circ x_2\circ ... \circ x_n. Consider the language L = \{x \in \Sigma ^* | \pi(x) = id\}. The minimum number of states in any DFA accepting L is _________ .Q10.
Consider the following language. L={x \in \{a,b\}^*| number of a's in x divisible by 2 but not divisible by 3} The minimum number of states in DFA that accepts L is _______